1. Field of the Invention
The present invention relates to a method of drawing parametric curve, more particularly, to a method of drawing parametric curve such as Bezier curve or B-spline curve expressed by cubic equation on the two-dimensional coordinate having coordinate value defined by discrete value.
2. Description of Related Art
When drawing either curves or straight lines with an apparatus for drawing two-dimensional plane composed of x and y axes, there are two methods of expressing coordinates of these axes. One of these is called "non-parametric curve" whose coordinates (x and y) are expressed in the form of f(x, y)=0. The other is called "parametric curve" whose coordinates are expressed in the form of x=g(t) and y=h(t), where t designates parameter.
Nevertheless, data on the surface of an image-drawing apparatus like coordinate values on a CRT display or a printing paper for example are not defined as continuous values, but in many cases, these values are defined by means of integral discrete values. The image-drawing apparatus of this type does not need to fully compute coordinate value of curve, but it may solely compute coordinates (lattice points) of integral coordinate values on curves or adjacent points. In order to compute the coordinate for drawing non-parametric curve, there is a method called "algorithm of Bresenham". FIG. 1 illustrates the algorithm of Bresenham. As shown here, when computing the ensuing points after drawing certain points (xn, yn), in accordance with the predetermined evaluation method, an optimal point is selected from adjacent 8 points having values of coordinates x and y differing from each other by 1. When the apparatus follows up selection of the optimal point from the startup point to the end point, all the points needed for drawing curve can be secured. Nevertheless, this is hardly applicable to the parametric curve. This is because the coordinate values of the parametric curve are solely defined by function of parameter t. As a result, it is difficult for the above conventional method to determine lattice points having values of coordinates x and y differing from each other by 1. For example, the Bezier curve available for expressing outlines of characters and figures is defined by the form shown below. ##EQU1## where (0.ltoreq.t.ltoreq.1) and x.sub.0, x.sub.1, x.sub.2, x.sub.3, y.sub.0, y.sub.1, y.sub.2, and y.sub.3, respectively designate coordinate values of four control points (x.sub.0, y.sub.0), (x.sub.1, y.sub.1), (x.sub.2, y.sub.2), and (x.sub.3, y.sub.3) determining the form.
Prior to the formation of this curve, the conventional apparatus needs to compute either Y-coordinate or X-coordinate having value x or y different from each other by 1 in correspondence with the incline at the objective coordinate. To compute either the Y-coordinate or the X-coordinate having the value x or y different from each other by 1, the apparatus needs to determine the value of parameter t by solving cubic equations related to x(t) or y(t), and then substitute the parameter value t into y(t) or x(t) before eventually computing y or x. Nevertheless, it takes much time to solve cubic equations, and thus, it is not ideal to spend much time merely for solving cubic equations when operating such an image drawing apparatus requiring extremely fast data-processing potential. Typically, there is a conventional method of drawing parametric curve disclosed in the Japanese Laid-Open Patent Publication No. 64-82282 of 1989. This method applies the algorithm of Bresenham to the drawing of Bezier curve, and thus, this method determines the parameter t by linear approximation in place of solving cubic equation.
This method is described below.
FIGS. 2 and 3 graphically illustrate the method mentioned above. In FIG. 2, the parameter t is designated on the axis of abscissa, whereas x(t) or y(t) is designated on the axis of ordinate. FIG. 2(a) illustrates x(t), whereas FIG. 2(b) illustrates y(t). FIG. 3 illustrates the curve-drawn pattern. The reference character BO shown in FIG. 3 designates the drawing startup point. When logically and correctly applying the algorithm of Bresenham, those points B1 through B4 are taken into consideration for continuous drawing points. In addition, adjacent points A1, A2, and A3 are secured. Referring to the points B1 and B2, since the preceding points B0 and B1 respectively have specific incline values (differential coefficient of x against y) being more than 1, the coordinate value of y is integral. Conversely, since the incline value at the point B3 is less than 1, the coordinate value of x is integral at the point B4. On the other hand, according to the prior invention disclosed in the Japanese Laid-Open Patent Publication No. 64-82282 of 1989, if the incline value is more than 1, then y(t) shown in FIG. 2(b) is subject to linear approximation. If the incline value is less than 1, then x(t) shown in FIG. 2(a) is subject to linear approximation so that those points approximating the points B.sub.1, B.sub.2, and B.sub.3 can be yielded. On the other hand, the value t.sub.1 of t is computed in order that the value of Y-coordinate at tangent L of y(t) at B.sub.0 (t=0) shown in FIG. 2(b) can become integer. Then, the point T.sub.1 shown in FIG. 3 in the condition of t=t.sub.1 is specified as the point approximating B.sub.1. These sequential processes are repeated until points T.sub.2 and T.sub.3 are determined as points approximating B.sub.2 and B.sub.3.
Furthermore, there is a conventional method of drawing Bezier curve, which initially sets .DELTA.t=1/2.sup.n (where n designates positive integer), and then computes coordinates X and Y by incrementing the value of the parameter t from t=0 up to t=1 by the amount .DELTA.t before specifying the nearest lattice points as the curve-drawing points x and y. FIG. 4 graphically illustrates this conventional method, in which C.sub.0, C.sub.1, . . . are respectively the points on the curve corresponding to t=0, t=.DELTA.t, t=2.DELTA.t, and t=3.DELTA.t. D.sub.0, D.sub.1, . . . respectively the rounded lattice points nearest to those points C.sub.0, C.sub.1, . . . Cn.
Nevertheless, as is obvious from FIG. 3, because the former conventional method can hardly secure accuracy of approximation, T.sub.2 is too far from B.sub.2. In consequence, F.sub.2 is selected as the adjacent point instead of the lattice point A.sub.2 which is closest to the curve.
On the other hand, if .DELTA.t is too small in the application of the later conventional method, redundant point is generated. FIG. 5(a) graphically illustrates the case in which a redundant point is generated. Black spots shown in FIG. 5 respectively designate those points on the Bezier curve, whereas white circles and circle F respectively designate rounded points. Although F is the lattice point closest to point G of the Bezier curve, the result of drawing is by far smoother when point F is deleted of drawing F. This is resulted from the method of selecting the nearest lattice point. Although the value of inclined curve is less than 1, two points are rounded on the identical coordinate x.sub.2 and on the different coordinates y.sub.2 and y.sub.3. When applying this method, since the rounded points are not always adjacent to each other, in the event that these points are apart from each other, interpolation with a straight line is necessary. FIG. 5(b) graphically illustrates this example, in which E.sub.0 and E.sub.3 respectively designate the rounded drawing points, whereas H.sub.1 and H.sub.2 respectively designate points generated by the linear interpolation between E.sub.0 and E.sub.3. Substantially, H.sub.1 and H.sub.2 are the lattice points nearest to the straight line passing through E.sub.0 and E.sub.3. Nevertheless, as shown in FIG. 5, when applying this method H.sub.2 has been selected for drawing curve instead in this case, instead that point J.sub.2 which is nearer to the curve than the point H.sub.2 should have been drawn.
In summary, the former conventional method cannot provide the curve with the nearest lattice point. On the other hand, the latter conventional method generates redundant point and cannot properly execute linear interpolation.